package com.company.linkedList;


import java.util.HashSet;
import java.util.Set;

public class IntersectionNode {
   public ListNode getIntersectionNode(ListNode headA,ListNode headB){
        return findByRevert(headA, headB);
   }

   private ListNode findByRevert(ListNode h1,ListNode h2){
       ListNode head1 = revertList(h1);
       ListNode head2 = revertList(h2);

       if (head1!=head2) {
           return null;
       }

       ListNode pointNode = head1;
       ListNode compareNode = head2;
       ListNode resultNode=head1;
       while (pointNode!=null&& compareNode!=null&&pointNode == compareNode){
           resultNode = pointNode;

           pointNode = pointNode.next;
           compareNode = compareNode.next;

       }
       return resultNode;
   }

    /**
     * 第一种方法 遍历更改每一个元素的 next 指向
     */
    private ListNode revertList(ListNode head) {
        ListNode pre;
        ListNode cur;
        ListNode next;
        pre = null;
        cur = head;
        while (cur != null) {
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }

   private ListNode findBySet(ListNode h1,ListNode h2){

       ListNode node=h1;
       Set<ListNode> set = new HashSet<>();
       while (node!=null){
//           if (set.contains(node)) {
//               return node;
//           }
           set.add(node);
           node = node.next;
       }
        node = h2;
       while (node!=null){
           if (set.contains(node)) {
               return node;
           }
           set.add(node);
           node = node.next;
       }
       return null;
   }
}
